#include "BiTree.h"
TNode *BuyTreeNode(DataType val)
{
    TNode *newnode = (TNode *)malloc(sizeof(TNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
    }
    newnode->data_ = val;
    newnode->left_ = newnode->right_ = NULL;
    return newnode;
}

// 二叉树前序遍历
void PreOrder(TNode *root)
{
    if (root == NULL)
        return;
    printf("%d ", root->data_);
    PreOrder(root->left_);
    PreOrder(root->right_);
}
// 二叉树中序遍历
void InOrder(TNode *root)
{
    if (root == NULL)
        return;
    PreOrder(root->left_);
    printf("%d ", root->data_);
    PreOrder(root->right_);
}
// 二叉树后序遍历
void PostOrder(TNode *root)
{
    if (root == NULL)
        return;
    PreOrder(root->left_);
    PreOrder(root->right_);
    printf("%d ", root->data_);
}
// 二叉树层序遍历
void LevelOrder(TNode *root)
{
    Queue q;
    InitQueue(&q);
    if (root != NULL)
        Push(&q, root);
    while (!Empty(&q))
    {
        TNode *tmp = NULL;
        Pop(&q, &tmp);
        printf("%d ", tmp->data_);
        if (tmp->left_)
            Push(&q, tmp->left_);
        if (tmp->right_)
            Push(&q, tmp->right_);
    }
}

// 二叉树节点个数
int BinaryTreeSize(TNode *root)
{
    if (root == NULL)
        return 0;
    return BinaryTreeSize(root->left_) + BinaryTreeSize(root->right_) + 1;
}
// 二叉树叶子节点个数
int BinaryTreeLeafSize(TNode *root)
{
    if (root == NULL)
        return 0;
    if (root->left_ == NULL && root->right_ == NULL)
        return 1;
    return BinaryTreeLeafSize(root->left_) + BinaryTreeLeafSize(root->right_);
}
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(TNode *root, int k)
{
    if (root == NULL)
        return 0;
    if (k == 1)
        return 1;
    return BinaryTreeLevelKSize(root->left_, k - 1) + BinaryTreeLevelKSize(root->right_, k - 1);
}
// 二叉树查找值为x的节点
TNode *BinaryTreeFind(TNode *root, DataType x)
{
    if (root == NULL)
        return NULL;
    if (root->data_ == x)
        return root;
    TNode *tmp1 = BinaryTreeFind(root->left_, x);
    TNode *tmp2;
    if (tmp1 == NULL)
    {
        tmp2 = BinaryTreeFind(root->right_, x);
        return tmp2;
    }
    else
    {
        return tmp1;
    }
}

void BinaryTreeDestory(TNode **root)
{
    if ((*root) == NULL)
        return;
    BinaryTreeDestory(&((*root)->left_));
    BinaryTreeDestory(&((*root)->right_));
    free(*root);
    *root = NULL;
}
// 求二叉树的深度
int hight(TNode *root)
{
    if (root == NULL)
        return 0;
    int h1 = hight(root->left_);
    int h2 = hight(root->right_);
    return h1 > h2 ? h1 + 1 : h2 + 1;
}
// 通过前序遍历的数组 "ABD##E#H##CF##G##"构建二叉树
TNode *BinaryTreeCreate(DataType *a, int *pi)
{
    if (a[*pi] == 0)
        return NULL;
    TNode *root = BuyTreeNode(a[*pi]);
    (*pi)++;
    root->left_ = BinaryTreeCreate(a, pi);
    (*pi)++;
    root->right_ = BinaryTreeCreate(a, pi);
    return root;
}